class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        // 老师的版本
        // 对nums1排序(升序)
        sort(nums1.begin(), nums1.end());

        int n = nums1.size();
        // 对nums2按下标排序
        vector<int> index_nums2(n);
        for(int i = 0; i < n; i++)
            index_nums2[i] = i;

        sort(index_nums2.begin(), index_nums2.end(), [&](int i, int j){ return nums2[i] < nums2[j]; });

        vector<int> ret(n);
        // 田忌赛马
        int left = 0, right = n - 1;
        for(int &x : nums1)
        {
            if(x > nums2[index_nums2[left]])
                ret[index_nums2[left++]] = x;
            else
                ret[index_nums2[right--]] = x;
        }
        return ret;

        // 田忌赛马(下面是B站网友解法，我翻译成C++的版本)
        // set<int> set;
        // unordered_map<int, int> hash;
        // int n = nums1.size();
        // for(int &x : nums1)
        // {
        //     hash[x]++;
        //     set.insert(x);
        // }

        // sort(nums1.begin(), nums1.end());

        // vector<int> ret;
        // for(int &x : nums2)
        // {
        //     // 在nums1中找到第一个大于x的元素
        //     // equal_range()：返回一对迭代器，这对迭代器是用一个pair存起来的
        //     // 分别表示第一个大于或等于给定关键值的元素和第一个大于给定关键值的元素
        //     // 第一个是键的 lower_bound，第二个是键的 upper_bound
        //     // 如果这一对定位器中哪个返回失败，则返回 end()

        //     auto p = set.equal_range(x);
            
        //     // 因为我们找的是第一个大于x的元素，所以我们应该使用第二个键
        //     if(p.second == set.end())
        //     {
        //         // 找不到，返回最小值
        //         p = set.equal_range(-1);
        //     }

        //     ret.push_back(*p.second);
        //     if(--hash[*p.second] == 0)
        //         set.erase(*p.second);

        // }
        // return ret;
    }
};